import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @program: data_structures_algorithms
 * @description: 中缀表达式转后缀表达式
 * @author: lld
 * @create: 2020/08/18 15:48
 **/
public class InfixToSuffixExpression {
    public static void main(String[] args) {
        String a = "(10+1)*5-12/3";//[10,1,+,5,*,12,3,/,-]=51
        List<String> infixList = toInfixExpressionList(a);
        List<String> suffixList = infixToSuffix(infixList);
        int calculate = SuffixExpression.calculate(suffixList);
        System.out.println("原中缀表达式:" + a);
        System.out.println("中缀表达式list:" + infixList);
        System.out.println("后缀表达式list:" + suffixList);
        System.out.println("表达式的值:" + calculate);
    }

    //方法：将 中缀表达式转成对应的List
    public static List<String> toInfixExpressionList(String s) {
        List<String> list = new ArrayList<>();
        String str;//用于字符转换
        int i = 0; //这时是一个指针，用于遍历 中缀表达式字符串
        while (i < s.length()) {
//            是运算符
            if (s.charAt(i) < 48 || s.charAt(i) > 57) {
                list.add(s.charAt(i) + "");
                i++;
            } else {
//                考虑多位数
                str = "";//当下次进入时，将原来str置空
                while ((i < s.length()) && (s.charAt(i) >= 48) && (s.charAt(i) <= 57)) {
                    str += s.charAt(i);//拼接
                    i++;
                }
                list.add(str);
            }
        }
        return list;
    }

    public static List<String> infixToSuffix(List<String> list) {
        //初始化两个栈：运算符栈s1和储存中间结果的栈s2；
        //栈s2可以用List代替，以便输出
        Stack<String> s1 = new Stack<>();
        List<String> s2 = new ArrayList<>();
        /**
            从左至右扫描中缀表达式；
            遇到操作数时，将其压s2；
            遇到运算符时，比较其与s1栈顶运算符的优先级：
            如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
            否则，若优先级比栈顶运算符的高，也将运算符压入s1；
            否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
            遇到括号时：
                (1) 如果是左括号“(”，则直接压入s1
                (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
            重复步骤2至5，直到表达式的最右边
            将s1中剩余的运算符依次弹出并压入s2
            依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

        */
//        1.从左至右扫描中缀表达式；
        for (String item : list) {
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                while (!s1.peek().equals("(")) {
                    //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2,直到遇到左括号为止
                    s2.add(s1.pop());
                }
                s1.pop();//!!! 将 ( 弹出 s1栈， 消除小括号
            } else {
                while (s1.size() != 0 && Operation.getValue(item) <= Operation.getValue(s1.peek()) && Operation.getValue(item) > 0 && Operation.getValue(s1.peek()) > 0) {
                    //优先级比栈顶运算符的低，将s1栈顶的运算符弹出并压入到s2中,再和s1栈顶运算符比较(+-*/)
                    s2.add(s1.pop());
                }
                //若优先级比栈顶运算符的高，也将运算符压入s1
                s1.push(item);
            }
        }
        //将s1中剩余的运算符依次弹出并压入s2
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        return s2;
    }
}

//定义操作符的优先级
class Operation {
    private static final int OTHER = 0;
    private static final int ADD = 1;
    private static final int SUB = 1;
    private static final int MUL = 2;
    private static final int DIV = 2;

    //写一个方法，返回对应的优先级数字
    public static int getValue(String oper) {
        int res = 0;
        switch (oper) {
            case "+":
                res = ADD;
                break;
            case "-":
                res = SUB;
                break;
            case "*":
                res = MUL;
                break;
            case "/":
                res = DIV;
                break;
            default:
                res = OTHER;
                break;
        }
        return res;
    }

}